package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer'>二进制链表转整数(Convert Binary Number in a Linked List to Integer)</a>
 * <p>给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。</p>
 * <p>请你返回该链表所表示数字的 十进制值 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,0,1]
 *      输出：5
 *      解释：二进制数 (101) 转化为十进制数 (5)
 *
 * 示例 2：
 *      输入：head = [0]
 *      输出：0
 *
 * 示例 3：
 *      输入：head = [1]
 *      输出：1
 *
 * 示例 4：
 *      输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
 *      输出：18880
 *
 * 示例 5：
 *      输入：head = [0,0]
 *      输出：0
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表不为空。</li>
 *     <li>链表的结点总数不超过 30。</li>
 *     <li>每个结点的值不是 0 就是 1。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/8 17:32
 */
public class LC1290ConvertBinaryNumberInLinkedListToInteger_S {
    static class Solution {
        public int getDecimalValue(ListNode head) {
            // 反正链表，反转后prev是链表头
            ListNode prev = null;
            ListNode curr = head;
            ListNode next;
            while (curr != null) {
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            int res = 0;
            for (int idx = 0; idx < 32 && prev != null; idx++, prev = prev.next) {
                res |= (prev.val << idx);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(0);
        head1.next.next = new ListNode(1);

        ListNode head2 = new ListNode(0);

        ListNode head3 = new ListNode(1);

        ListNode head4 = new ListNode(1);
        head4.next = new ListNode(0);
        head4.next.next = new ListNode(0);
        head4.next.next.next = new ListNode(1);
        head4.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next = new ListNode(1);
        head4.next.next.next.next.next.next.next = new ListNode(1);
        head4.next.next.next.next.next.next.next.next = new ListNode(1);
        head4.next.next.next.next.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next.next.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next.next.next.next.next.next.next.next = new ListNode(0);
        head4.next.next.next.next.next.next.next.next.next.next.next.next.next.next = new ListNode(0);

        ListNode head5 = new ListNode(0);
        head5.next = new ListNode(0);

        Solution solution = new Solution();
        System.out.println(solution.getDecimalValue(head1));
        System.out.println(solution.getDecimalValue(head2));
        System.out.println(solution.getDecimalValue(head3));
        System.out.println(solution.getDecimalValue(head4));
        System.out.println(solution.getDecimalValue(head5));
    }
}